# 冒泡排序： 像冒泡泡一样，每次一个数滚到后面去
# 时间复杂度: O(N^2)

def bubble_sort(nums):
    n = len(nums)
    for i in range(n):
        # 标记每轮是否有元素交换
        swapped = False
        for j in range(n - i - 1):
            if nums[j] > nums[j + 1]:
                # 交换元素
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        # 如果没有交换，数组已经有序，退出循环
        if not swapped:
            break
    return nums
